/*
 public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {
    public ListNode deleteDuplication(ListNode pHead) {
        if (pHead == null) {
            return null;
        } 
        ListNode dummy = pHead;
        ListNode pre = new ListNode(-1);
        pre.next = dummy;
        ListNode ret = pre;

        while (dummy.next != null) {
            if (dummy.val == dummy.next.val) {
                dummy = dummy.next;
            }
            else {
                if (pre.next != dummy) {
                    dummy = dummy.next;
                    pre.next = dummy;
                }
                else {
                    pre = dummy;
                    dummy = dummy.next;
                }
            }
        }
        if (pre.next != dummy) {
            dummy = dummy.next;
            pre.next = dummy;
        }

        return ret.next;

        /*
        //空链表
        if(pHead == null)
            return null;
        ListNode res = new ListNode(0);
        //在链表前加一个表头
        res.next = pHead;
        ListNode cur = res;
        while(cur.next != null && cur.next.next != null){
            //遇到相邻两个节点值相同
            if(cur.next.val == cur.next.next.val){
                int temp = cur.next.val;
                //将所有相同的都跳过
                while (cur.next != null && cur.next.val == temp)
                    cur.next = cur.next.next;
            }
            else
                cur = cur.next;
        }
        //返回时去掉表头
        return res.next;
        */

        // hash表
        /*
        //空链表
        if(pHead == null)
            return null;
        Map<Integer,Integer> mp = new HashMap<>();
        ListNode cur = pHead;
        //遍历链表统计每个节点值出现的次数
        while(cur != null){
            if(mp.containsKey(cur.val))
                mp.put(cur.val, (int)mp.get(cur.val) + 1);
            else
                mp.put(cur.val,1);
            cur = cur.next;
        }
        ListNode res = new ListNode(0);
        //在链表前加一个表头
        res.next = pHead;
        cur = res;
        //再次遍历链表
        while(cur.next != null){
            //如果节点值计数不为1
            if(mp.get(cur.next.val) != 1)
                //删去该节点
                cur.next = cur.next.next;
            else
                cur = cur.next;
        }
        //去掉表头
        return res.next;
        */
    }
}
